/**数组转树形结构 - 测试用例1 根元素无parent_id */
export const arrToTree_testData1 = [
    { "id": 12, "parent_id": 1, "name": "朝阳区" },
    { "id": 241, "parent_id": 24, "name": "田林街道" },
    { "id": 31, "parent_id": 3, "name": "广州市" },
    { "id": 13, "parent_id": 1, "name": "昌平区" },
    { "id": 2421, "parent_id": 242, "name": "上海科技绿洲" },
    { "id": 21, "parent_id": 2, "name": "静安区" },
    { "id": 242, "parent_id": 24, "name": "漕河泾街道" },
    { "id": 22, "parent_id": 2, "name": "黄浦区" },
    { "id": 11, "parent_id": 1, "name": "顺义区" },
    { "id": 2, "name": "上海市" },
    { "id": 24, "parent_id": 2, "name": "徐汇区" },
    { "id": 1, "name": "北京市" },
    { "id": 2422, "parent_id": 242, "name": "漕河泾开发区" },
    { "id": 32, "parent_id": 3, "name": "深圳市" },
    { "id": 33, "parent_id": 3, "name": "东莞市" },
    { "id": 3, "name": "广东省" }
]
/**数组转树形结构 - 测试用例2 根元素有parentId */
export const arrToTree_testData2 = [
    { "id": 12, "parentId": 1, "name": "朝阳区" },
    { "id": 241, "parentId": 24, "name": "田林街道" },
    { "id": 31, "parentId": 3, "name": "广州市" },
    { "id": 13, "parentId": 1, "name": "昌平区" },
    { "id": 2421, "parentId": 242, "name": "上海科技绿洲" },
    { "id": 21, "parentId": 2, "name": "静安区" },
    { "id": 242, "parentId": 24, "name": "漕河泾街道" },
    { "id": 22, "parentId": 2, "name": "黄浦区" },
    { "id": 11, "parentId": 1, "name": "顺义区" },
    { "id": 2, "parentId": 0, "name": "上海市" },
    { "id": 24, "parentId": 2, "name": "徐汇区" },
    { "id": 1, "parentId": 0, "name": "北京市" },
    { "id": 2422, "parentId": 242, "name": "漕河泾开发区" },
    { "id": 32, "parentId": 3, "name": "深圳市" },
    { "id": 33, "parentId": 3, "name": "东莞市" },
    { "id": 3, "parentId": 0, "name": "广东省" }
]

type treeData<T> = (T & { children?: T[] })

/**数组转树形结构，支持不同类型的主键和父键
 * @param arr 待转换数组
 * @param idKeyName 元素的主键
 * @param parentKeyName 元素的父元素索引的键名
 * @param root 根元素的主键 （可以不填，代表无 parentKeyName 的就是根元素）
 * @returns 转换好的新对象数组，孩子放在children中
 * @example 
 * const obj = arrToTree(arrToTree_testData1, 'id', 'parent_id')
 * console.log(obj);
 * const obj2 = arrToTree(arrToTree_testData2, 'id', 'parentId', 2) //根元素有parentId的时候，需要传递root
 * console.log(obj2);
 */
export function arrToTree<T extends Record<string, any>, key extends keyof T>(arr: T[], idKeyName: key, parentKeyName: keyof T, root?: T[key]): treeData<T>[] {

    //哈希表缓存法 - 时间复杂度O(n)  --  记录缓存遍历一次，递归遍历一次，共2n

    /**缓存记录每个元素的映射，键是父亲id，值是该父亲的孩子数组 */
    const cache = new Map<T[key], T[]>()
    /**没有parent的，或者parent等于root的 */
    const rootList: T[] = []
    for (let i = 0; i < arr.length; i++) {
        const element = arr[i];
        //不是根节点的，就存入缓存，是根节点的就放入rootList
        if (element[parentKeyName] != undefined && element[parentKeyName] !== root) {
            const arr = cache.get(element[parentKeyName as key]) || []
            arr.push(element)
            cache.set(element[parentKeyName as key], arr)
        } else {
            rootList.push(element)
        }
    }
    // console.log(cache, rootList);

    const digui = (list: T[]): treeData<T>[] => {
        return list.map((k) => {
            const children = digui(cache.get(k[idKeyName]) || [])
            if (children && children.length) return { ...k, children }
            else return { ...k }
        })
    }
    return digui(rootList)

    //普通递归法 - 缺点：每个元素会被遍历多次，时间复杂度高
    // const fn = (arr: T[], root: T[key]) => { 
    //     //递归法 - 缺点：每个元素会被遍历多次
    //     return arr
    //         .filter((k) => k[parentKeyName] === root || k[parentKeyName] == undefined)//找出所有根节点 （没有父级的，或者父级是指定的数据的）
    //         .map((k) => {
    //             const newArr = arr.filter((item) => k !== item) //优化 - 减少递归遍历数量
    //             return { ...k, children: fn(newArr, k[idKeyName]) }
    //         }) //递归孩子节点，放入children数组中
    // }
    // return fn(arr, root)
} 